package test

/**
 * User: bigbully
 * Date: 15/2/15
 * Time: 下午9:23
 */
object MyTree extends App{

//  println(depth(Branch(Branch(Leaf(1), Branch(Leaf(5), Leaf(3))), Leaf(2))))
  val tree = Branch(Branch(Leaf(1), Branch(Leaf(5), Leaf(3))), Leaf(2))
  println(map(tree)("a" + _.toString + "a"))



  sealed trait Tree[+A]
  case class Leaf[A](value: A) extends Tree[A]
  case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A]

  def size[A](tree:Tree[A]) = {
    def computeSize[A](tree:Tree[A]):Int = {
      tree match {
        case Leaf(value) => 1
        case Branch(left, right) => computeSize(left) + computeSize(right)
      }
    }
    computeSize(tree) + 1
  }

  def maximum(tree:Tree[Int]):Int = {
      tree match {
        case Leaf(value) => value
        case Branch(left, right) => maximum(left).max(maximum(right))
      }
  }


  def depth(tree:Tree[Int]):Int = {
    def findDepth(tree:Tree[Int]):Int = {
      tree match {
        case Leaf(_) => 0
        case Branch(left, right) => 1 + (findDepth(left) max findDepth(right))
      }
    }
    findDepth(tree)
  }

  def map[T, B](tree:Tree[T])(f:T => B):Tree[B] = {
    tree match {
      case Leaf(t) => Leaf(f(t))
      case Branch(left, right) => Branch(map(left)(f), map(right)(f))
    }
  }

  def fold[A, B](tree:Tree[A])(f:A=>B)(g:(B, B) => B) :B = {
    tree match {
      case Leaf(v) => f(v)
      case Branch(left, right) => g(fold(left)(f)(g), fold(right)(f)(g))
    }
  }

  def size1[A](tree:Tree[A]) = {
    fold(tree)(x => 1)(_ + _)
  }

}
